package basic.courseLearn08.problem;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

//金条分割问题
public class GoldSegment {

    //使用哈夫曼树求解
    public Integer solve(int[] nums) {
        //1. 定义小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new MinComparator());
        int result=0;
        //2. 数组填入
        for (int num : nums) {
            minHeap.add(num);
        }
        //3. 循环
        while(true){
            //3.1 取出两个最小值
            Integer num1 = (minHeap.size()!=0)?minHeap.poll():0;
            Integer num2 = (minHeap.size()!=0)?minHeap.poll():0;
            result+=num1+num2;
            //3.2 判断是否满足退出循环条件
            if (minHeap.size()==0){
                break;
            }
            //3. 将num1+num2放入堆中
            minHeap.add(num1+num2);
        }
        return result;
    }


    class MinComparator implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1-o2;
        }
    }


    @Test
    public void test(){
        int[] nums = {10,20,30,40,50};
        int result = solve(nums);
        System.out.println(result);
    }


}
